/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

import java.util.*;

/**
 *
 * @author Administrator
 */
public class LC242 {

    static class TreeNode {

        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class ListNode {

        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public class Solution {

        /**
         * @param root the root of binary tree
         * @return a lists of linked list
         */
        public List<ListNode> binaryTreeToLists(TreeNode root) {
            List<ListNode> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            Queue< TreeNode> q = new LinkedList<>();
            q.add(root);

            while (q.size() > 0) {
                int size = q.size();
                ListNode node = null;
                ListNode tail = node;

                for (int i = 0; i < size; i++) {
                    TreeNode pop = q.poll();
                    if (node == null) {
                        node = new ListNode(pop.val);
                        tail = node;
                    } else {
                        ListNode newNode = new ListNode(pop.val);
                        tail.next = newNode;
                        tail = newNode;
                    }

                    if (pop.left != null) {
                        q.add(pop.left);
                    }

                    if (pop.right != null) {
                        q.add(pop.right);
                    }

                }

                ans.add(node);
            }
            return ans;
        }
    }

}
